package com.shr.code_interview;

public class Solution_33 {
    public boolean VerifySquenceOfBST(int [] sequence) {
    	if(sequence == null || sequence.length == 0)
    		return false ;
    	
        int rootVal = sequence[sequence.length - 1];
        int leftIdx = 0;
        while(sequence[leftIdx] < rootVal && leftIdx < sequence.length)
        	leftIdx ++ ;
        for(int i = leftIdx; i<sequence.length-1; i++){
        	if(sequence[i] < rootVal)
        		return false;
        }
        
        boolean leftFlag = true ;
        if(leftIdx > 0){
        	int[] leftSequence = new int[leftIdx];
        	System.arraycopy(sequence, 0, leftSequence, 0, leftIdx);
        	leftFlag = VerifySquenceOfBST(leftSequence);
        }
        
        boolean rightFlag = true;
        if(leftIdx < sequence.length - 1){
        	int[] rightSequence = new int[sequence.length - leftIdx - 1];
        	System.arraycopy(sequence, leftIdx, rightSequence, 0, rightSequence.length - 1);
        	rightFlag = VerifySquenceOfBST(rightSequence) ;
        }
        
        return leftFlag && rightFlag ;
        	
    }
}
